#include <bits/stdc++.h>

using namespace std;

class Solution {
    public:
        string subStrHash(string s, int power, int mod, int k, int hashValue) {
            int n = s.length();
            // 用秦九韶算法计算 s[n-k:] 的哈希值，同时计算 pk=power^k
            long long hash = 0, pk = 1;
            for (int i = n - 1; i >= n - k; i--) {
                hash = (hash * power + (s[i] & 31)) % mod;
                pk = pk * power % mod;
            }
            int ans = hash == hashValue ? n - k : 0;
            // 向左滑窗
            for (int i = n - k - 1; i >= 0; i--) {
                // 计算新的哈希值，注意 +mod 防止计算出负数
                hash = (hash * power + (s[i] & 31) - pk * (s[i + k] & 31) % mod + mod) % mod;
                if (hash == hashValue) {
                    ans = i;
                }
            }
            return s.substr(ans, k);
        }
    };    
// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/find-substring-with-given-hash-value/solutions/1239542/dao-xu-hua-dong-chuang-kou-o1-kong-jian-xpgkp/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// class Solution
// {
// public:
//     string subStrHash(string s, int power, int modulo, int k, int hashValue)
//     {
//         int n = s.size();
//         auto val = [](char x)
//         { return x - 'a' + 1; };
//         long long windows = 0, pp = 1;
//         power %= modulo;
//         int ans = 0x3f3f3f3f;
//         for (int i = n - k; i < n; ++i){
//             windows = (windows + val(s[i]) * pp) % modulo;
//             if(i != n - 1)
//                 pp = (pp * power) % modulo;
//         }
//         // cout << windows << endl;
//         if (windows == hashValue)
//         {
//             ans = n - k;
//         }
//         for (int r = n - 1; r >= k; --r)
//         { // r 是即将出走的
//             int l = r - k;
//             windows = (modulo + windows - (val(s[r]) * pp % modulo)) % modulo;
//             windows = ((windows * power) % modulo + val(s[l])) % modulo;
//             if(windows == hashValue){
//                 ans = l;
//             }
//         }
//         // cout << ans << " ";
//         // return "";
//         return ans == 0x3f3f3f3f ? "" : s.substr(ans, k);
//     }
// };